//
// Created by Administrator on 2024/7/18.
/*前中后缀表达式介绍:
 * https://www.geeksforgeeks.org/expression-evaluation/
 * Evaluate an expression represented by a String. The expression can contain parentheses, you can assume parentheses are well-matched. For simplicity, you can assume only binary operations allowed are +, -, *, and /. Arithmetic Expressions can be written in one of three forms:

    Infix Notation: Operators are written between the operands they operate on, e.g. 3 + 4.
    Prefix Notation: Operators are written before the operands, e.g + 3 4
    Postfix Notation: Operators are written after operands.

 中文介绍: https://www.cnblogs.com/guo-ke/p/16786783.html
 https://blog.csdn.net/AngelDg/article/details/104526308
 四则表达式：8+5*(7-1)-8/2
 后缀表达式：8571-*+82/-
 ☆后缀表达式的计算原理:从左到右遍历表达式的每个数字和符号，遇到的是数字就进栈，遇到的是符号，就将栈顶的两个数字依次出栈，进行运算（运算规则：次栈顶 符号 栈顶），再将运算结果进栈，直到获得最终结果
 ☆中缀转后缀:
    1.初始化两个栈：运算符栈S1和储存中间结果的栈S2；
    2.从左至右扫描中缀表达式；
    3.遇到操作数时，将其压入S2；
    4.遇到运算符时，比较其与S1栈顶运算符的优先级：
        4.1 如果S1为空，或栈顶运算符为左括号“(”，则压入S1；
        4.2 比栈顶高，也将运算符压入S1 （注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
        4.3 比S1栈顶低或相同，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
    5.遇到括号时:
        5.1 如果是左括号“(”，则直接压入S1；
        5.2 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
    可以想象成“（”比任何运算符都高，“）”比任何运算符都低。
    6.重复步骤(2)至(5)，直到表达式的最右边；
    7.将S1中剩余的运算符依次弹出并压入S2；
    8.依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
 *
 * */
//

#include <iostream>
#include <vector>
#include <stack>
#include <map>

using namespace std;

// 计算后缀表达式
int calculate_postfix(string s)
{
    stack<int> st;
    for (char i : s)
    {
        if (i >= '0' && i <= '9')
            st.push(i-'0');
        else
        {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            if (i == '+')
                st.push(b + a);
            else if(i=='-')
                st.push(b - a);
            else if(i=='*')
                st.push(b * a);
            else if(i=='/')
                st.push(b / a);
        }
    }
    return st.top();
}

// 中缀--> 后缀
// https://oj.youdao.com/problem/626?from=problems
string infix_post(string str)
{
    // s1
    stack<char> s1,s2;
    map<char,int> level;
    level['(']=10;
    level['*']=7;
    level['/']=7;
    level['+']=6;
    level['-']=6;
    level[')']=0;
    for(char i: str)
    {
        // 3.遇到操作数时，将其压入S2；
        if ((i>='0' && i<='9') || (i>='A' && i<='Z'))
            s2.push(i);
        // 4.遇到运算符时，比较其与S1栈顶运算符的优先级：
        else{
            // 4.1如果S1为空，或栈顶运算符为左括号“(”，4.2 比栈顶高则压入S1
            if (s1.empty() || i=='(' ||s1.top()=='(' || level[i]>level[s1.top()])
                s1.push(i);
            else if(i==')')
            {
                // 5.2是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
                while(s1.top()!='(')
                {
                    char t = s1.top();
                    s1.pop();
                    s2.push(t);
                }
                s1.pop();
            }
            else{
                //4.3 比s1栈顶低或相同，将S1栈顶的运算符弹出并压入到S2中，再次转到(4.1)与S1中新的栈顶运算符相比较；
                while ( !s1.empty() && level[i]<=level[s1.top()])
                {
                    char t = s1.top();
                    s1.pop();
                    s2.push(t);
                }
                s1.push(i);
            }
        }
    }
    while(!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    string ans;
    while(!s2.empty())
    {
        // 倒着放入ans 就是后缀表达式 反之是前缀表达式
        ans=s2.top()+ans;
        s2.pop();
    }
    return ans;
}

int main()
{
    string infix_notation = "8+5*(7-1)-8/2"; // 8571-*+82/-
//    infix_notation="8-2"; // 82-
//    infix_notation = "(3+4)*5-6"; // 34+5×6-
    infix_notation="X+A*(Y-B)-Z/F"; // XAYB-*+ZF/-
//    infix_notation = "8-(3+2*6)/5+4"; // 8 3 2 6 * + 5 / - 4 +
//    cin>>infix_notation;

    string postfix_notation="25*39+6/-"; // 8
//    cout<<calculate_postfix(postfix_notation)<<endl;
    cout<<infix_post(infix_notation)<<endl;
    return 0;
}